|
The "Instant Insanity" puzzle consists of four cubes with faces colored with four colors (commonly red, blue, green, and white). The objective of the puzzle is to stack these cubes in a column so that each side (front, back, left, and right) of the stack shows each of the four colors. The distribution of colors on each cube is unique. This problem has a graph-theoretic solution in which a graph with four vertices labeled B, G, R, W (for blue, green, red, and white) can be used to represent each cube; there is an edge between two vertices if the two colors are on the opposite sides of the cube, and a loop at a vertex if the opposite sides have the same color. Trial and error is a slow way to solve this problem, as there are 41,472 arrangements of the four cubes, only one of which is a solution. A generalized version of the puzzle with more than four cubes is NP-complete.〔 (problem GP15);〕〔.〕 The puzzle was created by Franz Owen Armbruster, also known as Frank Armbruster, and published by Parker Brothers in 1967. Over 12 million puzzles were sold. The puzzle is isomorphic to numerous older puzzles, among them the ''Katzenjammer'' puzzle,〔http://home.comcast.net/~stegmann/pattern.htm〕 patented〔U.S. Patent 646,463〕 by Frederick A. Schossow in 1900, and ''The Great Tantalizer'' (circa 1940, and the most popular name prior to ''Instant Insanity''). The puzzle is currently being marketed by Winning Moves. ==A Solution to the problem with four cubes== Given the already colored cubes and the four distinct colors are (Red, Green, Blue, Yellow), we will try to generate a graph which gives a clear picture of all the positions of colors in all the cubes. The resultant graph will contain four vertices one for each color and we will number each edge from one through four (one number for each cube). If an edge connects two vertices (Red and Green) and the number of the edge is three, then it means that the third cube has Red and Green faces opposite to each other. Image 1 shows four cubes and their colors. Image 2 shows the graph generated by the four cubes. To find a solution to this problem we need the arrangement of four faces of each of the cubes. To represent the information of two opposite faces of all the four cubes we need a directed sub graph. Because two directions can only represent two opposite faces. So if we have two directed sub graphs, we can actually represent all the four faces (which matter) of all the four cubes. * First directed graph will represent the front and rear faces. * Second directed graph will represent the left and right faces. We cannot randomly select any two sub graphs - so what is the criteria for selecting? We need to choose graphs such that: # the two sub graphs have no edges in common, because if there is an edge which is common that means at least one cube has the pair of opposite faces of exactly same color. Meaning: A cube has Red and Blue as front and rear face as well as left and right face. # a sub graph contains only one edge from each cube, because the sub graph has to account for all the cubes and one edge can completely represent a pair of opposite faces. # a sub graph can contain only vertices of degree two, because a degree of two means a color can only be present at faces of two cubes. Easy way to understand is that there are eight faces to be equally divided into four colors. So, two per color. After understanding these restrictions if we try to derive the two sub graphs, we may end up with one possible set as shown in Image 3. Each edge color represents a cube. From the first sub graph we will derive the front and the rear face colors of the corresponding cube. For e.g.: # The black arrow from Yellow to Blue says that the first cube will have Yellow in the front face and Blue at the Rear. # The blue arrow from Green to Yellow says that the second cube will have Green in the front face and Yellow at the Rear. # The orange arrow from Blue to Red says that the third cube will have Blue in the front face and Red at the Rear. # The purple arrow from Red to Green says that the fourth cube will have Red in the front face and Green at the Rear. From the second sub graph we will derive the left and the right face colors of the corresponding cube. For e.g.: # The black arrow from Red to Green says that the first cube will have Red in the left face and Green at the Right. # The blue arrow from Blue to Red says that the first cube will have Blue in the left face and Red at the Right. # The orange arrow from Yellow to Blue says that the first cube will have Yellow in the left face and Blue at the Right. # The purple arrow from Green to Yellow says that the first cube will have Green in the left face and Yellow at the Right. The third image shows the derived stack of cube which is the solution to the problem. ==References== * 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Instant Insanity」の詳細全文を読む スポンサード リンク
|